package leetcode.code1080;

import leetcode.helper.H;
import leetcode.helper.tree.TreeArray;
import leetcode.helper.tree.TreeNode;

import leetcode.IDebug;

public class Solution implements IDebug {

	int limit;

	int NaN = Integer.MIN_VALUE;

	public TreeNode sufficientSubset(TreeNode root, int limit) {
		if (root == null) {
			return null;
		}
		this.limit = limit;
		int l = this.f(root.left, root.val);
		int r = this.f(root.right, root.val);
		if (l == NaN || root.val + l < limit) {
			root.left = null;
		}
		if (r == NaN || root.val + r < limit) {
			root.right = null;
		}
		int sum = Math.max(l, r) + root.val;
		return sum >= limit ? root : null;
	}

	private int f(TreeNode root, int val) {
		if (root == null) {
			return NaN;
		}
		int cur = root.val + val;
		int l = this.f(root.left, cur);
		int r = this.f(root.right, cur);
		if (l == NaN || cur + l < limit) {
			root.left = null;
		}
		if (r == NaN || cur + r < limit) {
			root.right = null;
		}
		if (l == NaN && r == NaN) {
			return root.val;
		}
		return Math.max(l, r) + root.val;
	}

	@Override
	public void debug4() {
		this.sufficientSubset(TreeArray.array2tree(H.str2array4("[5,4,8,11,null,17,4,7,1,null,null,5,3]")), 22);
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
